#pragma once

#include <cassert>
#include <climits>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>

namespace ezstl {

// sgi 一级配置器
template <int inst>
class malloc_alloc_template {
 public:
  using size_type = std::size_t;
  using pointer = void *;

 private:
  // function ptr
  // 用来处理内存不足的情况
  // oom: out of memory
  static void *oom_malloc(size_type n) {
    void (*my_malloc_handler)() = nullptr;
    void *result = nullptr;
    for (;;) {  // 不断尝试释放，配置，再释放，再配置
      my_malloc_handler = malloc_alloc_oom_handler;
      if (nullptr == my_malloc_handler) {
        fprintf(stderr, "out of memory\n");
        exit(1);
      }
      (*my_malloc_handler)();      // 调用处理例程，企图释放内存
      result = (void *)malloc(n);  // 再次尝试配置内存
      if (result) return (result);
    }
  }
  static void *oom_realloc(void *p, size_type n) {
    void (*my_malloc_handler)() = nullptr;
    void *result = nullptr;

    for (;;) {
      my_malloc_handler = malloc_alloc_oom_handler;
      if (nullptr == my_malloc_handler) {
        fprintf(stderr, "out of memory\n");
        exit(1);
      }
      (*my_malloc_handler)();
      result = (void *)realloc(p, n);
      if (result) return (result);
    }
  }
  using malloc_handler_type = void (*)();
  // static void (*malloc_alloc_oom_handler)();
  static malloc_handler_type malloc_alloc_oom_handler;

 public:
  static pointer allocate(size_type n) {
    void *result = (void *)malloc(n);
    if (nullptr == result) result = oom_malloc(n);
    return result;
  }

  static void deallocate(pointer p, size_type) { free(p); }

  static pointer reallocate(pointer p, size_type old_sz, size_type new_sz) {
    void *result = (void *)realloc(p, new_sz);
    if (nullptr == result) result = oom_realloc(p, new_sz);
    return result;
  }
  /* static void (*set_malloc_handler(void (*f)()))() {
    void (*old) () = malloc_alloc_oom_handler;
    malloc_alloc_oom_handler = f;
    return old;
  } */
  static malloc_handler_type set_malloc_handler(malloc_handler_type f) {
    malloc_handler_type old = malloc_alloc_oom_handler;
    malloc_alloc_oom_handler = f;
    return old;
  }
};

template <int inst>
void (*malloc_alloc_template<inst>::malloc_alloc_oom_handler)() = 0;

using malloc_alloc = malloc_alloc_template<0>;

// sgi 二级配置器
template <bool threads, int inst>
class default_alloc_template {
 public:
  using size_type = std::size_t;
  enum { ALIGN = 8, MAX_BYTES = 128, NFREELISTS = MAX_BYTES / ALIGN };

 private:
  union obj {  // free-lists 节点
    union obj *free_list_link;
    char client_data[1];
  };

 private:
  // 将 bytes 上调至 8 的倍数
  static size_type ROUND_UP(size_type bytes) {
    return (bytes + ALIGN - 1) & ~(ALIGN - 1);
  }

 private:
  // 16 个free-list
  static obj *volatile free_list[NFREELISTS];
  // 根据 bytes 大小， 决定使用第 n 号free-list
  static size_type FREELIST_INDES(size_type bytes) {
    return ((bytes + ALIGN - 1) / ALIGN - 1);
  }

  // 返回一个大小为 n 的对象，并可能将其加入大小为 n 的 free-list
  static void *refill(size_type n);
  // 分配可容纳nobjs个size大小对象的内存块。若无法满足请求数量，将酌情减少nobjs
  static char *chunk_alloc(size_type size, int &nobjs);

  // Memory Pool
  // Chunk allocation state
  static char *start_free;  // 内存池起始位置，只在 chunk_alloc 中变化
  static char *end_free;    // 内存池结束位置，只在 chunk_alloc 中变化
  static size_type heap_size;

 public:
  static void *allocate(size_type n);
  static void deallocate(void *p, size_type n);
  static void *reallocate(void *p, size_type old_sz, size_type new_sz);
};

template <bool threads, int inst>
char *default_alloc_template<threads, inst>::start_free = nullptr;
template <bool threads, int inst>
char *default_alloc_template<threads, inst>::end_free = nullptr;
template <bool threads, int inst>
std::size_t default_alloc_template<threads, inst>::heap_size = 0;
/*
free-list:
+---+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 8 |
+---+---+---+---+---+---+---+---+
  |
  |
+---+ : chunk
|   |
+---+
|   |
+---+
*/
template <bool threads, int inst>
typename default_alloc_template<threads, inst>::obj
    *volatile default_alloc_template<threads, inst>::free_list[NFREELISTS] = {
        nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr,
        nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr};

using default_alloc = default_alloc_template<false, 0>;

template <bool threads, int inst>
void *default_alloc_template<threads, inst>::allocate(size_type size) {
  obj *volatile *my_free_list = nullptr;
  obj *result = nullptr;

  // 大于 128 调用一级配置器
  if (size > MAX_BYTES) return (malloc_alloc::allocate(size));

  // 寻找 16 个 free-list 中合适的一个
  my_free_list = free_list + FREELIST_INDES(size);
  result = *my_free_list;
  if (nullptr == result) {
    // 没有找到可用的 free-list，重新填充 free-list
    void *r = refill(ROUND_UP(size));
    return r;
  }
  *my_free_list = result->free_list_link;
  return (result);
}

template <bool threads, int inst>
void default_alloc_template<threads, inst>::deallocate(void *p,
                                                       size_type size) {
  obj *q = (obj *)p;
  obj *volatile *my_free_list = nullptr;

  if (size > MAX_BYTES) return malloc_alloc::deallocate(p, size);

  my_free_list = free_list + FREELIST_INDES(size);
  // 头插法
  q->free_list_link = *my_free_list;
  *my_free_list = q;
}

template <bool threads, int inst>
void *default_alloc_template<threads, inst>::reallocate(void *p,
                                                        size_type old_sz,
                                                        size_type new_sz) {
  void *result;
  size_t copy_sz;
  if (old_sz > MAX_BYTES && new_sz > MAX_BYTES) {
    return malloc_alloc::reallocate(p, old_sz, new_sz);
  }
  if (ROUND_UP(old_sz) == ROUND_UP(new_sz)) return p;
  result = allocate(new_sz);
  copy_sz = (old_sz < new_sz) ? old_sz : new_sz;
  memcpy(result, p, copy_sz);
  deallocate(p, old_sz);
  return result;
}

template <bool threads, int inst>
void *default_alloc_template<threads, inst>::refill(size_type size) {
  int n_objs = 20;
  char *chunk = chunk_alloc(size, n_objs);
  obj *volatile *my_free_list = nullptr;

  obj *result = nullptr;
  obj *current_obj = nullptr, *next_obj = nullptr;
  int i = 0;

  if (n_objs == 1) return chunk;

  my_free_list = free_list + FREELIST_INDES(size);
  result = (obj *)chunk;  // 准备返回使用
  *my_free_list = next_obj =
      (obj *)(chunk + size);  // FIXME: (obj *)chunk + size --> now
  // 第 0 个返回 使用
  for (i = 1;; i++) {
    current_obj = next_obj;
    next_obj = (obj *)((char *)next_obj + size);
    if (n_objs - 1 == i) {
      current_obj->free_list_link = nullptr;
      break;
    } else {
      current_obj->free_list_link = next_obj;
    }
  }

  return result;
}

template <bool threads, int inst>
char *default_alloc_template<threads, inst>::chunk_alloc(size_type size,
                                                         int &nobjs) {
  char *result = nullptr;
  size_type total_bytes = size * nobjs;
  size_type bytes_left = end_free - start_free;  // 内存池剩余空间
  if (bytes_left >= total_bytes) {               // 内存池剩余空间满足需求量
    result = start_free;
    start_free += total_bytes;  // FIXME: none --> now
    return (result);
  } else if (bytes_left >= size) {  // 内存池中的空间只够供应一个以上的 块
    nobjs = bytes_left / size;
    total_bytes = size * nobjs;
    result = start_free;
    start_free += total_bytes;
    return (result);
  } else {
    size_type bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
    if (bytes_left > 0) {
      // 先将内存池中剩下的内存分配给对应的 free-list
      obj *volatile *my_free_list = free_list + FREELIST_INDES(bytes_left);
      ((obj *)start_free)->free_list_link = *my_free_list;
      *my_free_list = (obj *)start_free;
    }
    // 重新分配内存池
    start_free = (char *)malloc(bytes_to_get);
    if (nullptr == start_free) {
      // malloc 分配失败 就从free-list
      // 尚有未用区块，且足够大的free-list中挖出一块
      int i = 0;
      obj *volatile *my_free_list, *p;
      for (i = size; i <= MAX_BYTES; i += ALIGN) {
        my_free_list = free_list + FREELIST_INDES(i);
        p = *my_free_list;
        if (nullptr != p) {
          *my_free_list = p->free_list_link;
          start_free = (char *)p;
          end_free = start_free + i;
          return (chunk_alloc(size, nobjs));
        }
      }
      end_free = 0;  // 出现意外 实在没有内存可用了
      // 调用一级配置器，看 oom 机制能否尽点力
      start_free = (char *)malloc_alloc::allocate(bytes_to_get);
    }
    heap_size += bytes_to_get;
    end_free = start_free + bytes_to_get;
    // 调用自己，为了修正 nobjs
    return (chunk_alloc(size, nobjs));
  }
}

#if 0
template <typename T>
class new_malloc_template {
 public:
  using size_type = std::size_t;
  using pointer = void *;

 public:
  static pointer allocate(size_type n) {
    return static_cast<pointer>(operator new(n));
  }
  static void deallocate(pointer p) { operator delete(p); }
  static pointer reallocate(pointer p, size_type old_sz, size_type new_sz) {
    pointer result = allocate(new_sz);
    memmove(result, p, old_sz > new_sz ? new_sz : old_sz);
    deallocate(p);
    return result;
  }
};
#endif

template <typename T, typename BaseAlloc = default_alloc>
class debug_alloc {
 public:
  static size_t allocate_size;
  static size_t deallocate_size;
  static size_t reallocate_size;

  static void print_stat() {
    std::cout << "allocate_size: " << allocate_size << std::endl;
    std::cout << "deallocate_size: " << deallocate_size << std::endl;
    std::cout << "reallocate_size: " << reallocate_size << std::endl;
    std::cout << "total_size: "
              << allocate_size + deallocate_size + reallocate_size << std::endl;
    assert(allocate_size == deallocate_size + reallocate_size);
  }

 private:
  static const size_t EXTRA = sizeof(size_t *);

 public:
  static void *allocate(size_t n) {
    std::cout << "\033[33m[DEBUG]\033[0m allocate n = " << n
              << ", count = " << n / sizeof(T) << std::endl;
    char *result = (char *)BaseAlloc::allocate(n + (int)EXTRA);
    std::cout << "\033[33m[DEBUG]\033[0m " << "allocate address: " << std::hex
              << (void *)result
              << ", real address: " << (void *)(result + (int)EXTRA) << std::dec
              << std::endl;
    allocate_size += n + EXTRA;
    *(size_t *)result = n;
    return result + (int)EXTRA;
  }

  static void deallocate(void *p, size_t n) {
    char *real_p = (char *)p - (int)EXTRA;
    std::cout << "\033[33m[DEBUG]\033[0m deallocate real_n = "
              << *(size_t *)real_p << " n = " << n
              << ", count = " << n / sizeof(T) << std::endl;
    std::cout << "\033[33m[DEBUG]\033[0m " << "deallocate address: " << std::hex
              << (void *)real_p << ", real address: " << (void *)p << std::dec
              << std::endl;
    deallocate_size += n + EXTRA;
    assert(*(size_t *)real_p == n);
    BaseAlloc::deallocate(real_p, n + (int)EXTRA);
  }

  static void *reallocate(void *p, size_t old_sz, size_t new_sz) {
    char *real_p = (char *)p - (int)EXTRA;
    assert(*(size_t *)real_p == old_sz);
    char *__result = (char *)BaseAlloc::reallocate(real_p, old_sz + (int)EXTRA,
                                                   new_sz + (int)EXTRA);
    std::cout << "\033[33m[DEBUG]\033[0m "
              << "reallocate old_n = " << old_sz << " new_n = " << new_sz
              << ", count = " << new_sz / sizeof(T) << std::endl;
    std::cout << "\033[33m[DEBUG]\033[0m "
              << "reallocate address: " << std::hex << (void *)real_p
              << ", result address: " << (void *)__result
              << ", real address: " << (void *)p << std::dec << std::endl;
    reallocate_size += new_sz + EXTRA;
    *(size_t *)__result = new_sz;
    return __result + (int)EXTRA;
  }
};
template <typename T, typename BaseAlloc>
size_t debug_alloc<T, BaseAlloc>::allocate_size = 0;
template <typename T, typename BaseAlloc>
size_t debug_alloc<T, BaseAlloc>::deallocate_size = 0;
template <typename T, typename BaseAlloc>
size_t debug_alloc<T, BaseAlloc>::reallocate_size = 0;

template <typename T, typename BaseAlloc = debug_alloc<T>>
class Allocator {
 public:
  using value_type = T;
  using size_type = std::size_t;
  using difference_type = std::ptrdiff_t;
  using pointer = value_type *;
  using const_pointer = const value_type *;
  using reference = value_type &;
  using const_reference = const value_type &;

 public:
  template <typename U>
  struct rebind {
    Allocator<U, BaseAlloc> other;
  };

 public:
  static pointer allocate(size_type n, const void *hint = 0) {
    // return static_cast<pointer>(operator new(n * sizeof(value_type)));
    auto res = static_cast<pointer>(
        n ? BaseAlloc::allocate(n * sizeof(value_type)) : nullptr);

    return res;
  }
  static void deallocate(pointer p, size_type n) {
    if (n) BaseAlloc::deallocate(p, n * sizeof(value_type));
  }
  static void deallocate(pointer p) {
    // operator delete(p);
    BaseAlloc::deallocate(p, sizeof(value_type));
  }

  static void construct(pointer p, const_reference value) {
    new (p) value_type(value);  // ctor for T;
  }
  static void destroy(pointer p) { p->~value_type(); }
  static pointer address(reference x) { return static_cast<pointer>(&x); }
  static const_pointer const_address(const_reference x) {
    return static_cast<const_pointer>(&x);
  }
  static size_type max_size() { return size_t(UINT_MAX / sizeof(value_type)); }
};

template <typename Alloc>
struct allocator_traits {
  using allocator_type = Alloc;
  using value_type = typename Alloc::value_type;
  using pointer = typename Alloc::pointer;
};

}  // namespace ezstl
